<!doctype html>
<html class="theme-next   use-motion ">
<head>
  <meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1"/>



<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />












  <link href="/vendors/fancybox/source/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css"/>




  <link href="//fonts.googleapis.com/css?family=Lato:300,400,700,400italic&subset=latin,latin-ext" rel="stylesheet" type="text/css">



<link href="/vendors/font-awesome/css/font-awesome.min.css?v=4.4.0" rel="stylesheet" type="text/css" />

<link href="/css/main.css?v=0.4.5.2" rel="stylesheet" type="text/css" />


  <meta name="keywords" content="algorithm,java,lruCache," />








  <link rel="shortcut icon" type="image/x-icon" href="/favicon.ico?v=0.4.5.2" />






<meta name="description" content="Implement LRU Cache

Wikipedia https://en.wikipedia.org/wiki/Cache_algorithms 
In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are op">
<meta property="og:type" content="article">
<meta property="og:title" content="Least-Recently-Used Cache">
<meta property="og:url" content="https://lechance.github.io/posts/2016/04/08/least-recently-used-cache/index.html">
<meta property="og:site_name" content="Lechance's Blog">
<meta property="og:description" content="Implement LRU Cache

Wikipedia https://en.wikipedia.org/wiki/Cache_algorithms 
In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are op">
<meta property="og:updated_time" content="2016-08-04T07:17:41.199Z">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Least-Recently-Used Cache">
<meta name="twitter:description" content="Implement LRU Cache

Wikipedia https://en.wikipedia.org/wiki/Cache_algorithms 
In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are op">



<script type="text/javascript" id="hexo.configuration">
  var CONFIG = {
    scheme: '',
    sidebar: 'hide',
    motion: true
  };
</script>

  <title> Least-Recently-Used Cache | Lechance's Blog </title>
</head>

<body itemscope itemtype="http://schema.org/WebPage" lang="en">

  <!--[if lte IE 8]>
  <div style=' clear: both; height: 59px; padding:0 0 0 15px; position: relative;margin:0 auto;'>
    <a href="http://windows.microsoft.com/en-US/internet-explorer/products/ie/home?ocid=ie6_countdown_bannercode">
      <img src="http://7u2nvr.com1.z0.glb.clouddn.com/picouterie.jpg" border="0" height="42" width="820"
           alt="You are using an outdated browser. For a faster, safer browsing experience, upgrade for free today or use other browser ,like chrome firefox safari."
           style='margin-left:auto;margin-right:auto;display: block;'/>
    </a>
  </div>
<![endif]-->
  


<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
            (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
          m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');
  ga('create', 'UA-75174040-1', 'auto');
  ga('send', 'pageview');
</script>


  <script type="text/javascript">
    var _hmt = _hmt || [];
    (function() {
      var hm = document.createElement("script");
      hm.src = "//hm.baidu.com/hm.js?5641a55459d47b98c90f424b8ca53a5a";
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(hm, s);
    })();
  </script>




  <div class="container one-column page-post-detail">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"><div class="site-meta ">
  

  <div class="custom-logo-site-title">
    <a href="/"  class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <span class="site-title">Lechance's Blog</span>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>
  <p class="site-subtitle"></p>
</div>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
  

  
    <ul id="menu" class="menu ">
      
        
        <li class="menu-item menu-item-home">
          <a href="/" rel="section">
            
              <i class="menu-item-icon fa fa-home fa-fw"></i> <br />
            
            Home
          </a>
        </li>
      
        
        <li class="menu-item menu-item-archives">
          <a href="/archives" rel="section">
            
              <i class="menu-item-icon fa fa-archive fa-fw"></i> <br />
            
            Archives
          </a>
        </li>
      
        
        <li class="menu-item menu-item-tags">
          <a href="/tags" rel="section">
            
              <i class="menu-item-icon fa fa-tags fa-fw"></i> <br />
            
            Tags
          </a>
        </li>
      
        
        <li class="menu-item menu-item-links">
          <a href="/links" rel="section">
            
              <i class="menu-item-icon fa fa-link fa-fw"></i> <br />
            
            Links
          </a>
        </li>
      
        
        <li class="menu-item menu-item-about">
          <a href="/about" rel="section">
            
              <i class="menu-item-icon fa fa-user fa-fw"></i> <br />
            
            About
          </a>
        </li>
      
        
        <li class="menu-item menu-item-rss">
          <a href="/atom.xml" rel="section">
            
              <i class="menu-item-icon fa fa-rss fa-fw"></i> <br />
            
            Rss
          </a>
        </li>
      

      
      
    </ul>
  

  
</nav>

 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div id="content" class="content">
          

  <div id="posts" class="posts-expand">
    

  
  

  
  
  

  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">

    
      <header class="post-header">

        
        
          <h1 class="post-title" itemprop="name headline">
            
            
              
                Least-Recently-Used Cache
              
            
          </h1>
        

        <div class="post-meta">
          <span class="post-time">
            Posted on
            <time itemprop="dateCreated" datetime="2016-04-08T18:58:16+08:00" content="2016-04-08">
              2016-04-08
            </time>
          </span>

          
            <span class="post-category" >
              &nbsp; | &nbsp; In
              
                <span itemprop="about" itemscope itemtype="https://schema.org/Thing">
                  <a href="/categories/Algorithm/" itemprop="url" rel="index">
                    <span itemprop="name">Algorithm</span>
                  </a>
                </span>

                
                

              
            </span>
          

          
            
              <span class="post-comments-count">
                &nbsp; | &nbsp;
                <a href="/posts/2016/04/08/least-recently-used-cache/#comments" itemprop="discussionUrl">
                  <span class="post-comments-count ds-thread-count" data-thread-key="posts/2016/04/08/least-recently-used-cache/" itemprop="commentsCount"></span>
                </a>
              </span>
            
          

          
		  
		  
			 &nbsp; | &nbsp;
			 <span id="/posts/2016/04/08/least-recently-used-cache/"class="leancloud_visitors"  data-flag-title="Least-Recently-Used Cache">
             &nbsp;Views
            </span>
		  
		
        </div>
      </header>
    


    <div class="post-body">

      
      

      
        <span itemprop="articleBody"><p>Implement LRU Cache</p>
<blockquote>
<p>Wikipedia <a href="https://en.wikipedia.org/wiki/Cache_algorithms" target="_blank" rel="external">https://en.wikipedia.org/wiki/Cache_algorithms</a> </p>
<p>In computing, cache algorithms (also frequently called cache replacement algorithms or cache replacement policies) are optimizing instructions—​​or algorithms—​​that a computer program or a hardware-maintained structure can follow in order to manage a cache of information stored on the computer. When the cache is full, the algorithm must choose which items to discard to make room for the new ones.</p>
</blockquote>
<p>The LRU caching scheme is to remove the least recently used frame when the cache is full and a new page is referenced which is not there in cache.</p>
<p>We use two data structures to implement an LRU Cache.</p>
<ol>
<li><p>A Queue which is implemented using a doubly linked list. </p>
</li>
<li><p>A Hash with node number as key and value of the corresponding queue node as value.</p>
</li>
</ol>
<p>Note: Initially no data is in the cache.</p>
<p>Below is Java implementation:<br><figure class="highlight java"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br><span class="line">176</span><br><span class="line">177</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.HashMap;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span><br><span class="line"> *  LruCacheDemo Created by lechance</span><br><span class="line"> */</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">LruCacheDemo</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String[] args)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">int</span> maxSize = <span class="number">5</span>;</span><br><span class="line">        LruCache&lt;Integer, Person&gt; lruCache = <span class="keyword">new</span> LruCache&lt;&gt;(maxSize);</span><br><span class="line"></span><br><span class="line">        <span class="comment">//entity</span></span><br><span class="line">        Person p1 = <span class="keyword">new</span> Person(<span class="string">"people 1"</span>);</span><br><span class="line">        Person p2 = <span class="keyword">new</span> Person(<span class="string">"people 2"</span>);</span><br><span class="line">        Person p3 = <span class="keyword">new</span> Person(<span class="string">"people 3"</span>);</span><br><span class="line">        Person p4 = <span class="keyword">new</span> Person(<span class="string">"people 4"</span>);</span><br><span class="line">        Person p5 = <span class="keyword">new</span> Person(<span class="string">"people 5"</span>);</span><br><span class="line"></span><br><span class="line">        Person p6 = <span class="keyword">new</span> Person(<span class="string">"people 6"</span>);</span><br><span class="line"></span><br><span class="line">        lruCache.put(<span class="number">1</span>, p1);</span><br><span class="line">        lruCache.put(<span class="number">2</span>, p2);</span><br><span class="line">        lruCache.put(<span class="number">3</span>, p3);</span><br><span class="line">        lruCache.put(<span class="number">4</span>, p4);</span><br><span class="line">        lruCache.put(<span class="number">5</span>, p5);</span><br><span class="line"></span><br><span class="line">        lruCache.put(<span class="number">6</span>, p6);</span><br><span class="line"></span><br><span class="line">        print(lruCache.get(<span class="number">1</span>)); <span class="comment">// it will print null because beyond the limit size</span></span><br><span class="line"></span><br><span class="line">        <span class="comment">//therefore, the following items can be acquired normally</span></span><br><span class="line">        print(p2);</span><br><span class="line">        print(p5);</span><br><span class="line">        print(p6);</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">//generic method for convenience print test-info</span></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> &lt;T&gt; <span class="function"><span class="keyword">void</span> <span class="title">print</span><span class="params">(T t)</span> </span>&#123;</span><br><span class="line">        System.out.println(t);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">static</span> <span class="class"><span class="keyword">class</span> <span class="title">Person</span> </span>&#123;</span><br><span class="line">        String name;</span><br><span class="line"></span><br><span class="line">        Person(String name) &#123;</span><br><span class="line">            <span class="keyword">this</span>.name = name;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="annotation">@Override</span></span><br><span class="line">        <span class="function"><span class="keyword">public</span> String <span class="title">toString</span><span class="params">()</span> </span>&#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="string">"Person: "</span> + name;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/**</span><br><span class="line"> * We can keep two separate data structures, A &lt;b&gt;HashMap with (key, pointers)&lt;/b&gt; pairs and a &lt;b&gt;</span><br><span class="line"> * doubly linked list&lt;/b&gt; which will work as the priority queue for deletion and store the &lt;b&gt;Values&lt;/b&gt;</span><br><span class="line"> * , From the &lt;b&gt;HashMap&lt;/b&gt;, we can point to an element in the doubly linked list and update it's retrieval</span><br><span class="line"> * time. Because we go directly from the &lt;b&gt;HashMap&lt;/b&gt; to the item in the list, our time complexity</span><br><span class="line"> * remains at O(1).</span><br><span class="line"> * &lt;p&gt;</span><br><span class="line"> * For example, our doubly linked list can look like:</span><br><span class="line"> * &lt;p&gt;</span><br><span class="line"> * Least-recently-used-link -&gt; A &lt;-&gt; B &lt;-&gt; C &lt;-&gt; D &lt;-&gt; E -&gt; most-recently-used-link</span><br><span class="line"> * --------------------------------------------------------------------------------</span><br><span class="line"> * left-side most -&gt;                   middle                 &lt;- right-side most</span><br><span class="line"> *</span><br><span class="line"> * <span class="doctag">@param</span> &lt;K&gt; The type of key</span><br><span class="line"> * <span class="doctag">@param</span> &lt;V&gt; The type of pointers (doubly linked list)</span><br><span class="line"> */</span></span><br><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">LruCache</span>&lt;<span class="title">K</span>, <span class="title">V</span>&gt; </span>&#123;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">static</span> <span class="keyword">final</span> Object mLock = <span class="keyword">new</span> Object();</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> mCurrentSize;</span><br><span class="line">    <span class="keyword">private</span> <span class="keyword">int</span> mMaxSize;</span><br><span class="line">    <span class="keyword">private</span> HashMap&lt;K, Node&lt;K, V&gt;&gt; mCache;</span><br><span class="line">    <span class="keyword">private</span> Node&lt;K, V&gt; mLeastRecentlyUsedNode;</span><br><span class="line">    <span class="keyword">private</span> Node&lt;K, V&gt; mMostRecentlyUsedNode;</span><br><span class="line"></span><br><span class="line">    <span class="comment">// the list is empty</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="title">LruCache</span><span class="params">(<span class="keyword">int</span> maxSize)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">this</span>.mMaxSize = maxSize;</span><br><span class="line">        mCurrentSize = <span class="number">0</span>;</span><br><span class="line">        mCache = <span class="keyword">new</span> HashMap&lt;&gt;();</span><br><span class="line">        mLeastRecentlyUsedNode = <span class="keyword">new</span> Node&lt;&gt;(<span class="keyword">null</span>, <span class="keyword">null</span>, <span class="keyword">null</span>, <span class="keyword">null</span>);</span><br><span class="line">        mMostRecentlyUsedNode = mLeastRecentlyUsedNode;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">void</span> <span class="title">put</span><span class="params">(K key, V value)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">if</span> (mCache.containsKey(key)) &#123;</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//put the new node at the right-most end of the linked list</span></span><br><span class="line">        Node&lt;K, V&gt; tempNode = <span class="keyword">new</span> Node&lt;&gt;(mMostRecentlyUsedNode, <span class="keyword">null</span>, key, value);</span><br><span class="line">        mMostRecentlyUsedNode.next = tempNode;</span><br><span class="line">        mMostRecentlyUsedNode = tempNode;</span><br><span class="line">        mCache.put(key, tempNode);</span><br><span class="line"></span><br><span class="line">        <span class="comment">//Delete the left-most entry if items exceed maxSize and update the LRU</span></span><br><span class="line">        <span class="keyword">if</span> (mCurrentSize == mMaxSize) &#123;</span><br><span class="line">            mCache.remove(mLeastRecentlyUsedNode.key);</span><br><span class="line">            mLeastRecentlyUsedNode = mLeastRecentlyUsedNode.next;</span><br><span class="line">            mLeastRecentlyUsedNode.previous = <span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// Update cache size, for the first added entry update the LRU pointer</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (mCurrentSize &lt; mMaxSize) &#123;</span><br><span class="line">            <span class="keyword">if</span> (mCurrentSize == <span class="number">0</span>) &#123;</span><br><span class="line">                mLeastRecentlyUsedNode = tempNode;</span><br><span class="line">            &#125;</span><br><span class="line">            mCurrentSize++;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> V <span class="title">get</span><span class="params">(K key)</span> </span>&#123;</span><br><span class="line"></span><br><span class="line">        Node&lt;K, V&gt; tempNode = mCache.get(key);</span><br><span class="line">        <span class="keyword">if</span> (tempNode == <span class="keyword">null</span>) &#123;</span><br><span class="line">            <span class="keyword">return</span> <span class="keyword">null</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// if MRU leave the list as it is</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (tempNode.key == mMostRecentlyUsedNode.key) &#123;</span><br><span class="line">            <span class="keyword">return</span> tempNode.value;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">        <span class="comment">// get the next and previous nodes</span></span><br><span class="line">        Node&lt;K, V&gt; previousNode = tempNode.previous;</span><br><span class="line">        Node&lt;K, V&gt; nextNode = tempNode.next;</span><br><span class="line"></span><br><span class="line">        <span class="comment">// If at the left-most(LRU), we update LRU</span></span><br><span class="line">        <span class="keyword">if</span> (tempNode.key == mLeastRecentlyUsedNode.key) &#123;</span><br><span class="line">            nextNode.previous = tempNode;</span><br><span class="line">            previousNode.previous = <span class="keyword">null</span>;</span><br><span class="line">            mLeastRecentlyUsedNode = nextNode;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="comment">// if we are at in middle, we need to update the items before and after</span></span><br><span class="line">        <span class="keyword">else</span> <span class="keyword">if</span> (tempNode.key != mMostRecentlyUsedNode.key) &#123;</span><br><span class="line">            previousNode.next = nextNode;</span><br><span class="line">            <span class="comment">//note that</span></span><br><span class="line">            previousNode.previous = nextNode;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="comment">//finally  move the item to the MRU</span></span><br><span class="line">        tempNode.previous = mMostRecentlyUsedNode;</span><br><span class="line">        mMostRecentlyUsedNode.next = tempNode;</span><br><span class="line">        mMostRecentlyUsedNode = tempNode;</span><br><span class="line">        mMostRecentlyUsedNode.next = <span class="keyword">null</span>;</span><br><span class="line"></span><br><span class="line">        <span class="keyword">return</span> tempNode.value;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span><br><span class="line">     * Define &#123;<span class="doctag">@code</span> Node&#125; with pointers to the previous and next item and a key, value</span><br><span class="line">     *</span><br><span class="line">     * <span class="doctag">@param</span> &lt;T&gt; the type of key</span><br><span class="line">     * <span class="doctag">@param</span> &lt;U&gt; the type of value</span><br><span class="line">     */</span></span><br><span class="line">    <span class="keyword">private</span> <span class="class"><span class="keyword">class</span> <span class="title">Node</span>&lt;<span class="title">T</span>, <span class="title">U</span>&gt; </span>&#123;</span><br><span class="line">        T key;</span><br><span class="line">        U value;</span><br><span class="line">        <span class="keyword">private</span> Node&lt;T, U&gt; previous;</span><br><span class="line">        <span class="keyword">private</span> Node&lt;T, U&gt; next;</span><br><span class="line"></span><br><span class="line">        Node(Node&lt;T, U&gt; previous, Node&lt;T, U&gt; next, T key, U value) &#123;</span><br><span class="line">            <span class="keyword">this</span>.previous = previous;</span><br><span class="line">            <span class="keyword">this</span>.next = next;</span><br><span class="line">            <span class="keyword">this</span>.key = key;</span><br><span class="line">            <span class="keyword">this</span>.value = value;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure></p>
<p>Origanize post from Network.</p>
</span>
      
    </div>

    <footer class="post-footer">
      
        <div class="post-tags">
          
            <a href="/tags/algorithm/" rel="tag">#algorithm</a>
          
            <a href="/tags/java/" rel="tag">#java</a>
          
            <a href="/tags/lruCache/" rel="tag">#lruCache</a>
          
        </div>
      

      
        <div class="post-nav">
          <div class="post-nav-next post-nav-item">
            
              <a href="/posts/2016/04/02/usage-of-volley-lib/" rel="next" title="Usage of The Volley Library in Android">
                <i class="fa fa-chevron-left"></i> Usage of The Volley Library in Android
              </a>
            
          </div>

          <div class="post-nav-prev post-nav-item">
            
              <a href="/posts/2016/04/15/android-http-client-get-post-download-upload-multipart-request/" rel="prev" title="ANDROID HTTP CLIENT-GET,POST,DOWNLOAD,UPLOAD,MULTIPART REQUEST">
                ANDROID HTTP CLIENT-GET,POST,DOWNLOAD,UPLOAD,MULTIPART REQUEST <i class="fa fa-chevron-right"></i>
              </a>
            
          </div>
        </div>
      

      
      
    </footer>
  </article>



    <div class="post-spread">
      
        <div class="ds-share flat" data-thread-key="posts/2016/04/08/least-recently-used-cache/"
     data-title="Least-Recently-Used Cache"
     data-content=""
     data-url="https://lechance.github.io/posts/2016/04/08/least-recently-used-cache/">
  <div class="ds-share-inline">
    <ul  class="ds-share-icons-16">

      <li data-toggle="ds-share-icons-more"><a class="ds-more" href="javascript:void(0);">分享到：</a></li>
      <li><a class="ds-weibo" href="javascript:void(0);" data-service="weibo">微博</a></li>
      <li><a class="ds-qzone" href="javascript:void(0);" data-service="qzone">QQ空间</a></li>
      <li><a class="ds-qqt" href="javascript:void(0);" data-service="qqt">腾讯微博</a></li>
      <li><a class="ds-wechat" href="javascript:void(0);" data-service="wechat">微信</a></li>

    </ul>
    <div class="ds-share-icons-more">
    </div>
  </div>
</div>
      
    </div>
  </div>


        </div>

        


        
  <div class="comments" id="comments">
    
      <div class="ds-thread" data-thread-key="posts/2016/04/08/least-recently-used-cache/"
           data-title="Least-Recently-Used Cache" data-url="https://lechance.github.io/posts/2016/04/08/least-recently-used-cache/">
      </div>
    
  </div>


      </div>

      
        
  
  <div class="sidebar-toggle">
    <div class="sidebar-toggle-line-wrap">
      <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
      <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
    </div>
  </div>

  <aside id="sidebar" class="sidebar">
    <div class="sidebar-inner">

      

      
        <ul class="sidebar-nav motion-element">
          <li class="sidebar-nav-toc sidebar-nav-active" data-target="post-toc-wrap" >
            Table Of Contents
          </li>
          <li class="sidebar-nav-overview" data-target="site-overview">
            Overview
          </li>
        </ul>
      

      <section class="site-overview sidebar-panel ">
        <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
          <img class="site-author-image" src="/upload/image/avatar.png" alt="Lechance Cheung" itemprop="image"/>
          <p class="site-author-name" itemprop="name">Lechance Cheung</p>
        </div>
        <p class="site-description motion-element" itemprop="description">The code to change the world</p>
        <nav class="site-state motion-element">
          <div class="site-state-item site-state-posts">
            <a href="/archives">
              <span class="site-state-item-count">43</span>
              <span class="site-state-item-name">posts</span>
            </a>
          </div>

          <div class="site-state-item site-state-categories">
            
              <span class="site-state-item-count">15</span>
              <span class="site-state-item-name">categories</span>
              
          </div>

          <div class="site-state-item site-state-tags">
            <a href="/tags">
              <span class="site-state-item-count">66</span>
              <span class="site-state-item-name">tags</span>
              </a>
          </div>

        </nav>

        

        <div class="links-of-author motion-element">
          
            
              <span class="links-of-author-item">
                <a href="http://weibo.com/lechance" target="_blank">
                  
                    <i class="fa fa-weibo"></i> Weibo
                  
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="https://github.com/lechance" target="_blank">
                  
                    <i class="fa fa-globe"></i> Github
                  
                </a>
              </span>
            
              <span class="links-of-author-item">
                <a href="https://guides.github.com/features/mastering-markdown/" target="_blank">
                  
                    <i class="fa fa-globe"></i> MD CheatSheet
                  
                </a>
              </span>
            
          
        </div>

        
        
          <div class="cc-license motion-element" itemprop="license">
            <a href="http://creativecommons.org/licenses/by-nc-sa/4.0" class="cc-opacity" target="_blank">
              <img src="/images/cc-by-nc-sa.svg" alt="Creative Commons" />
            </a>
          </div>
        

        <div class="links-of-author motion-element">
          
            <p class="site-author-name">Common Sites</p>
            
              <span class="links-of-author-item">
                <a href="https://developers.google.cn" target="_blank">Google Developers</a>
              </span>
            
              <span class="links-of-author-item">
                <a href="http://androidweekly.net/archive" target="_blank">Android Weekly</a>
              </span>
            
              <span class="links-of-author-item">
                <a href="https://rxjava.yuxingxin.com" target="_blank">RxJava Essentials</a>
              </span>
            
              <span class="links-of-author-item">
                <a href="https://hc.apache.org/index.html" target="_blank">Http Components</a>
              </span>
            
              <span class="links-of-author-item">
                <a href="http://simpledeveloper.com" target="_blank">Simple Developer</a>
              </span>
            
              <span class="links-of-author-item">
                <a href="https://www.ibm.com/developerworks/library" target="_blank">IBM(Technical Library)</a>
              </span>
            
          
        </div>

      </section>

      
        <section class="post-toc-wrap motion-element sidebar-panel sidebar-panel-active">
          <div class="post-toc-indicator-top post-toc-indicator">
            <i class="fa fa-angle-double-up"></i>
          </div>
          <div class="post-toc">
            
              
            
            
              <p class="post-toc-empty">This post does not have a Table Of Contents</p>
            
          </div>
          <div class="post-toc-indicator-bottom post-toc-indicator">
            <i class="fa fa-angle-double-down"></i>
          </div>
        </section>
      

    </div>
  </aside>


      
    </main>

    <footer id="footer" class="footer">
      <div class="google-ad">
	  <script async src="//pagead2.googlesyndication.com/pagead/js/adsbygoogle.js"></script>
<!-- myblogfootergooglead -->
<ins class="adsbygoogle"
     style="display:inline-block;width:468px;height:60px"
     data-ad-client="ca-pub-6226577131784709"
     data-ad-slot="6824128270"></ins>
<script>
(adsbygoogle = window.adsbygoogle || []).push({});
</script>

      </div>
      <div class="footer-inner">
        <script async src="https://dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js">
</script>

<div class="copyright" >
  
  &copy;  2015 - 
  <span itemprop="copyrightYear">2017</span>
  <span class="with-love">
    <i class="icon-next-heart fa fa-heart"></i>
  </span>
  <span class="author" itemprop="copyrightHolder">Lechance Cheung</span>
</div>

<div class="powered-by">
  Powered by <a class="theme-link" href="http://hexo.io">Hexo</a>
</div>

<div class="theme-info">
  Theme -
  <a class="theme-link" href="https://github.com/iissnan/hexo-theme-next">
    NexT
  </a>
</div>

<span id="busuanzi_container_site_pv">
  &nbsp; | &nbsp;PV <span id="busuanzi_value_site_pv"></span> &nbsp;| &nbsp;UV <span id="busuanzi_value_site_uv"></span>
</span>



      </div>
    </footer>

    <div class="back-to-top"></div>
  </div>

  <script type="text/javascript" src="/vendors/jquery/index.js?v=2.1.3"></script>

  
  

  
    

  
    
  

  <script type="text/javascript">
    var duoshuoQuery = {short_name:"lechance"};
    (function() {
      var ds = document.createElement('script');
      ds.type = 'text/javascript';ds.async = true;
      ds.id = 'duoshuo-script';
      ds.src = (document.location.protocol == 'https:' ? 'https:' : 'http:') + '//lechance.github.io/embed_ua.js';
      ds.charset = 'UTF-8';
      (document.getElementsByTagName('head')[0]
      || document.getElementsByTagName('body')[0]).appendChild(ds);
    })();
  </script>
    
     


    
  

  
  <script type="text/javascript" src="/vendors/fancybox/source/jquery.fancybox.pack.js"></script>
  <script type="text/javascript" src="/js/fancy-box.js?v=0.4.5.2"></script>


  <script type="text/javascript" src="/js/helpers.js?v=0.4.5.2"></script>
  <script type="text/javascript" src="/vendors/velocity/velocity.min.js"></script>
<script type="text/javascript" src="/vendors/velocity/velocity.ui.min.js"></script>

<script type="text/javascript" src="/js/motion.js?v=0.4.5.2" id="motion.global"></script>


  <script type="text/javascript" src="/vendors/fastclick/lib/fastclick.min.js?v=1.0.6"></script>
  <script type="text/javascript" src="/vendors/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>

  
  
<script type="text/javascript" src="/js/bootstrap.scrollspy.js?v=0.4.5.2" id="bootstrap.scrollspy.custom"></script>


<script type="text/javascript" id="sidebar.toc.highlight">
  $(document).ready(function () {
    var tocSelector = '.post-toc';
    var $tocSelector = $(tocSelector);
    var activeCurrentSelector = '.active-current';

    $tocSelector
      .on('activate.bs.scrollspy', function () {
        var $currentActiveElement = $(tocSelector + ' .active').last();

        removeCurrentActiveClass();
        $currentActiveElement.addClass('active-current');

        $tocSelector[0].scrollTop = $currentActiveElement.position().top;
      })
      .on('clear.bs.scrollspy', function () {
        removeCurrentActiveClass();
      });

    function removeCurrentActiveClass () {
      $(tocSelector + ' ' + activeCurrentSelector)
        .removeClass(activeCurrentSelector.substring(1));
    }

    function processTOC () {
      getTOCMaxHeight();
      toggleTOCOverflowIndicators();
    }

    function getTOCMaxHeight () {
      var height = $('.sidebar').height() -
                   $tocSelector.position().top -
                   $('.post-toc-indicator-bottom').height();

      $tocSelector.css('height', height);

      return height;
    }

    function toggleTOCOverflowIndicators () {
      tocOverflowIndicator(
        '.post-toc-indicator-top',
        $tocSelector.scrollTop() > 0 ? 'show' : 'hide'
      );

      tocOverflowIndicator(
        '.post-toc-indicator-bottom',
        $tocSelector.scrollTop() >= $tocSelector.find('ol').height() - $tocSelector.height() ? 'hide' : 'show'
      )
    }

    $(document).on('sidebar.motion.complete', function () {
      processTOC();
    });

    $('body').scrollspy({ target: tocSelector });
    $(window).on('resize', function () {
      if ( $('.sidebar').hasClass('sidebar-active') ) {
        processTOC();
      }
    });

    onScroll($tocSelector);

    function onScroll (element) {
      element.on('mousewheel DOMMouseScroll', function (event) {
          var oe = event.originalEvent;
          var delta = oe.wheelDelta || -oe.detail;

          this.scrollTop += ( delta < 0 ? 1 : -1 ) * 30;
          event.preventDefault();

          toggleTOCOverflowIndicators();
      });
    }

    function tocOverflowIndicator (indicator, action) {
      var $indicator = $(indicator);
      var opacity = action === 'show' ? 1 : 0;
      $indicator.velocity ?
        $indicator.velocity('stop').velocity({
          opacity: opacity
        }, { duration: 100 }) :
        $indicator.stop().animate({
          opacity: opacity
        }, 100);
    }

  });
</script>

<script type="text/javascript" id="sidebar.nav">
  $(document).ready(function () {
    var html = $('html');
    var TAB_ANIMATE_DURATION = 200;
    var hasVelocity = $.isFunction(html.velocity);

    $('.sidebar-nav li').on('click', function () {
      var item = $(this);
      var activeTabClassName = 'sidebar-nav-active';
      var activePanelClassName = 'sidebar-panel-active';
      if (item.hasClass(activeTabClassName)) {
        return;
      }

      var currentTarget = $('.' + activePanelClassName);
      var target = $('.' + item.data('target'));

      hasVelocity ?
        currentTarget.velocity('transition.slideUpOut', TAB_ANIMATE_DURATION, function () {
          target
            .velocity('stop')
            .velocity('transition.slideDownIn', TAB_ANIMATE_DURATION)
            .addClass(activePanelClassName);
        }) :
        currentTarget.animate({ opacity: 0 }, TAB_ANIMATE_DURATION, function () {
          currentTarget.hide();
          target
            .stop()
            .css({'opacity': 0, 'display': 'block'})
            .animate({ opacity: 1 }, TAB_ANIMATE_DURATION, function () {
              currentTarget.removeClass(activePanelClassName);
              target.addClass(activePanelClassName);
            });
        });

      item.siblings().removeClass(activeTabClassName);
      item.addClass(activeTabClassName);
    });

    $('.post-toc a').on('click', function (e) {
      e.preventDefault();
      var targetSelector = escapeSelector(this.getAttribute('href'));
      var offset = $(targetSelector).offset().top;
      hasVelocity ?
        html.velocity('stop').velocity('scroll', {
          offset: offset  + 'px',
          mobileHA: false
        }) :
        $('html, body').stop().animate({
          scrollTop: offset
        }, 500);
    });

    // Expand sidebar on post detail page by default, when post has a toc.
    motionMiddleWares.sidebar = function () {
      var $tocContent = $('.post-toc-content');
      if (CONFIG.sidebar === 'post') {
        if ($tocContent.length > 0 && $tocContent.html().trim().length > 0) {
          displaySidebar();
        }
      }
    };
  });
</script>



  <script type="text/javascript" src="/js/bootstrap.js"></script>

  
  

  
  
  
  
  	 <!-- custom analytics part create by xiamo -->
<script src="https://cdn1.lncld.net/static/js/av-core-mini-0.6.1.js"></script>
<script>AV.initialize("cHqcCBDQtcbkltuUTyplEYWJ-gzGzoHsz", "SkioJGixXR48ACpgA0W2lOWd");</script>
<script>
function showTime(Counter) {
	var query = new AV.Query(Counter);
	$(".leancloud_visitors").each(function() {
		var url = $(this).attr("id").trim();
		query.equalTo("url", url);
		query.find({
			success: function(results) {
				if (results.length == 0) {
					var content = '0 ' + $(document.getElementById(url)).text();
					$(document.getElementById(url)).text(content);
					return;
				}
				for (var i = 0; i < results.length; i++) {
					var object = results[i];
					var content = object.get('time') + ' ' + $(document.getElementById(url)).text();
					$(document.getElementById(url)).text(content);
				}
			},
			error: function(object, error) {
				console.log("Error: " + error.code + " " + error.message);
			}
		});

	});
}

function addCount(Counter) {
	var Counter = AV.Object.extend("Counter");
	url = $(".leancloud_visitors").attr('id').trim();
	title = $(".leancloud_visitors").attr('data-flag-title').trim();
	var query = new AV.Query(Counter);
	query.equalTo("url", url);
	query.find({
		success: function(results) {
			if (results.length > 0) {
				var counter = results[0];
				counter.fetchWhenSave(true);
				counter.increment("time");
				counter.save(null, {
					success: function(counter) {
						var content =  counter.get('time') + ' ' + $(document.getElementById(url)).text();
						$(document.getElementById(url)).text(content);
					},
					error: function(counter, error) {
						console.log('Failed to save Visitor num, with error message: ' + error.message);
					}
				});
			} else {
				var newcounter = new Counter();
				newcounter.set("title", title);
				newcounter.set("url", url);
				newcounter.set("time", 1);
				newcounter.save(null, {
					success: function(newcounter) {
					    console.log("newcounter.get('time')="+newcounter.get('time'));
						var content = newcounter.get('time') + ' ' + $(document.getElementById(url)).text();
						$(document.getElementById(url)).text(content);
					},
					error: function(newcounter, error) {
						console.log('Failed to create');
					}
				});
			}
		},
		error: function(error) {
			console.log('Error:' + error.code + " " + error.message);
		}
	});
}
$(function() {
	var Counter = AV.Object.extend("Counter");
	if ($('.leancloud_visitors').length == 1) {
		addCount(Counter);
	} else if ($('.post-title-link').length > 1) {
		showTime(Counter);
	}
}); 
</script>
  
  
<!-- mathjax config similar to math.stackexchange -->

<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    tex2jax: {
      inlineMath: [ ['$','$'], ["\\(","\\)"] ],
      processEscapes: true
    }
  });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Config({
      tex2jax: {
        skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
      }
    });
</script>

<script type="text/x-mathjax-config">
    MathJax.Hub.Queue(function() {
        var all = MathJax.Hub.getAllJax(), i;
        for(i=0; i < all.length; i += 1) {
            all[i].SourceElement().parentNode.className += ' has-jax';
        }
    });
</script>

<script type="text/javascript" src="//cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>
</body>
</html>
